package com.sheng.leetcode.year2022.month10.day26;

import org.junit.Test;

import java.util.ArrayList;
import java.util.Arrays;
import java.util.Collections;
import java.util.List;

/**
 * @author liusheng
 * @date 2022/10/26
 *<p>
 * 862. 和至少为 K 的最短子数组<p>
 *<p>
 * 给你一个整数数组 nums 和一个整数 k ，找出 nums 中和至少为 k 的 最短非空子数组 ，<p>
 * 并返回该子数组的长度。如果不存在这样的 子数组 ，返回 -1 。<p>
 * 子数组 是数组中 连续 的一部分。<p>
 *<p>
 * 示例 1：<p>
 * 输入：nums = [1], k = 1<p>
 * 输出：1<p>
 *<p>
 * 示例 2：<p>
 * 输入：nums = [1,2], k = 4<p>
 * 输出：-1<p>
 *<p>
 * 示例 3：<p>
 * 输入：nums = [2,-1,2], k = 3<p>
 * 输出：3<p>
 *<p>
 * 提示：<p>
 * 1 <= nums.length <= 10^5<p>
 * -10^5 <= nums[i] <= 10^5<p>
 * 1 <= k <= 10^9<p>
 */
public class LeetCode0862 {

    @Test
    public void test01() {
//        int[] nums = {1};
//        int k = 1;
//        int[] nums = {1, 2};
//        int k = 4;
//        int[] nums = {2,-1,2};
//        int k = 3;
        int[] nums = {17, 85, 93, -45, -21};
        int k = 150;
        System.out.println(new Solution().shortestSubarray(nums, k));
    }
}
// 暴力破解超时
//class Solution {
//    public int shortestSubarray(int[] nums, int k) {
//        int length = nums.length;
//        int ans = Integer.MAX_VALUE;
//        for (int i = 0; i < length; i++) {
//            int max = 0;
//            int sum = 0;
//            for (int j = i; j < length; j++) {
//                sum += nums[j];
//                max++;
//                if (sum >= k) {
//                    ans = Math.min(max, ans);
//                    break;
//                }
//            }
//        }
//        if (ans != Integer.MAX_VALUE) {
//            return ans;
//        } else {
//            return -1;
//        }
//    }
//}

class Solution {
    static int N = 200010;
    static int[] tr = new int[N], sum = new int[N];
    int n, m, ans;
    int lowbit(int x) {
        return x & -x;
    }
    void update(int val, int loc) {
        for (int i = val; i < m; i += lowbit(i)) {
            tr[i] = Math.max(tr[i], loc);
        }
    }
    int query(int x) {
        int ans = -1;
        for (int i = x; i > 0; i -= lowbit(i)) {
            ans = Math.max(ans, tr[i]);
        }
        return ans;
    }
    int getIdx(List<Long> list, long x) {
        int l = 0, r = list.size() - 1;
        while (l < r) {
            int mid = l + r >> 1;
            if (list.get(mid) >= x) {
                r = mid;
            } else {
                l = mid + 1;
            }
        }
        return r + 1;
    }
    public int shortestSubarray(int[] nums, int k) {
        n = nums.length; m = 2 * n + 10; ans = n + 10;
        Arrays.fill(tr, -1);
        long[] temp = new long[m];
        List<Long> list = new ArrayList<>();
        list.add(0L);
        for (int i = 1; i <= 2 * n + 1; i++) {
            if (i <= n) {
                temp[i] = temp[i - 1] + nums[i - 1];
            } else {
                temp[i] = temp[i - (n + 1)] + k;
            }
            list.add(temp[i]);
        }
        Collections.sort(list);
        for (int i = 0; i <= 2 * n + 1; i++) {
            sum[i] = getIdx(list, temp[i]);
        }
        update(sum[n + 1], 0);
        for (int i = 1; i <= n; i++) {
            int j = query(sum[i]);
            if (j != -1) {
                ans = Math.min(ans, i - j);
            }
            update(sum[n + 1 + i], i);
        }
        return ans == n + 10 ? -1 : ans;
    }
}
//
//作者：宫水三叶
//链接：https://leetcode.cn/problems/shortest-subarray-with-sum-at-least-k/solutions/1925325/by-ac_oier-es0s/
//来源：力扣（LeetCode）
//著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。
